#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	int N;
	cin >> N;
	while (N--) 
	{
		int X;
		int flag = 1;
		cin >> X;
		for (int i = 2; i <= sqrt(X); i++)
		{
			if (X % i == 0)
			{
				flag = 0;
			}
		}
		if (flag)
		{
			cout << X << " is prime" << endl;
		}
		else
		{
			cout << X << " is not prime" << endl;
		}
	}

	return 0;
}